package mytest;

public class Count_Occurrence {

	static int a[]={1,2,3,6,6,7};
	
	
	static int bsearch(int l,int r,int value,int flag)
	{
		while(l<=r)
		{	
			int mid=(l+r)>>1;
			if(flag==0)//找到相等的位置
			{
				if(a[mid]==value)
				{
					return mid;
				}else if(a[mid]<value)
				{
					l=mid+1;
				}else{
					r=mid-1;
				}
			}else if(flag==1)
			{//找上界
				if(a[mid]>value)
				{
					r=mid-1;
				}else{
					l=mid+1;
				}
				if(l>r)return r;
			}else{
				//找下界
				if(a[mid]<value)
				{
					l=mid+1;
				}else{
					r=mid-1;
				}
				if(l>r)return l;
			}
		}
		
		return -1;
	}
	
	
	static int count(int l,int r,int value)
	{
		if(l>r||a[l]>value||a[r]<value)return 0;
		if(a[l]==value&&a[r]==value){
			return r-l+1;
		}
		int mid=(l+r)>>1;
		return count(l,mid,value)+count(mid+1,r,value);
	}
	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int value=5;
		int pos=bsearch(0, a.length-1, value, 0);
		if(pos==-1)System.out.println("0");
		else{
			int lbound=bsearch(0, pos, value, -1);
			int rbound=bsearch(pos, a.length-1, value, 1);
			System.out.println(rbound-lbound+1);
		}
		
		System.out.println(count(0,a.length-1,value));
	}

}
